◀ Prev · Parts · Full · Next ▶

layout: Wide · Narrow · Centered

As a motivating example, consider the problem of finding an ‘a’ in an array of n elements.

Input: An array of n≥2 elements, in which half are ‘a’s and the other half are ‘b’s.

Output: Find an ‘a’ in the array.

We give two versions of the algorithm, one Las Vegas algorithm and one Monte Carlo algorithm.

Las Vegas algorithm:

This algorithm succeeds with probability 1. The number of iterations varies and can be arbitrarily large, but the expected number of iterations is

lim n → ∞ ∑ i = 1 n i 2 i = 2 {\displaystyle \lim _{n\to \infty }\sum _{i=1}^{n}{\frac {i}{2^{i}}}=2}

Since it is constant, the expected run time over many calls is Θ ( 1 ) {\displaystyle \Theta (1)} . (See Big Theta notation)

Monte Carlo algorithm:

If an ‘a’ is found, the algorithm succeeds, else the algorithm fails. After k iterations, the probability of finding an ‘a’ is:

Pr [ f i n d a ] = 1 − ( 1 / 2 ) k {\displaystyle \Pr[\mathrm {find~a} ]=1-(1/2)^{k}}

This algorithm does not guarantee success, but the run time is bounded. The number of iterations is always less than or equal to k. Taking k to be constant the run time (expected and absolute) is Θ ( 1 ) {\displaystyle \Theta (1)} .

Randomized algorithms are particularly useful when faced with a malicious "adversary" or attacker who deliberately tries to feed a bad input to the algorithm (see worst-case complexity and competitive analysis (online algorithm)) such as in the Prisoner's dilemma. It is for this reason that randomness is ubiquitous in cryptography. In cryptographic applications, pseudo-random numbers cannot be used, since the adversary can predict them, making the algorithm effectively deterministic. Therefore, either a source of truly random numbers or a cryptographically secure pseudo-random number generator is required. Another area in which randomness is inherent is quantum computing.

◀ Prev · Parts · Full · Next ▶